/*
 * @Author: vincent040 18620373040@163.com
 * @Date: 2023-08-13 11:15:32
 * @LastEditors: vincent040 18620373040@163.com
 * @LastEditTime: 2023-08-13 18:29:04
 * Copyright (c) 2023 by GEC, All Rights Reserved. 
 * @Description: 
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "queue.h"
#include "stack.h"

static int success;

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void permute(int arr[], int start, int end, int **result)
{
    static int count = 0;

    if (start == end)
    {
        for (int i = 0; i <= end; i++)
            result[count][i] = arr[i];
        count++;
    }
    else
    {
        for (int i = start; i <= end; i++)
        {
            swap(&arr[start], &arr[i]);
            permute(arr, start + 1, end, result );
            swap(&arr[start], &arr[i]); // Backtrack to restore the original order
        }
    }
}

void show(int *carriage, int n)
{
    for(int i=0; i<n; i++)
        fprintf(stderr, "%d ", carriage[i]);
}

bool is_valid(int *carriage, int n)
{
    show(carriage, n);

    // 将序列置入队列中
    linkqueue *q = init_queue();
    for(int i=0; i<n; i++)
        en_quene(q, carriage[i]);

    // 1. 将序列逐个入栈，并与队头比对
    // 2. 如果栈顶元素与队头元素相等，意味着成功配对，于是可以出栈、出队，重复第1步
    // 3. 如果栈顶元素与队头元素不相等，意味着不配对，那么继续入栈，重复第1步
    linkstack *s = init_stack();
    for(int i=n; i>=1; i--)
    {
        push(s, i);

        while(!stack_is_empty(s) && top(s)->data == queue_front(q)->data)
        {
            free(pop(s));
            free(out_queue(q));
        }
    }

    // 4. 当以上循环结束后，栈内元素为空，意味着全部配对成功，是合法出栈序列
    //    否则若站内元素不为空，则意味着该序列是不合法序列
    if(stack_is_empty(s))
    {
        success++;
        return true;
    }
    
    return false;
}

int main()
{
    // 1. 输入n节车厢
    int n;
    scanf("%d",&n);

    if(n <= 0)
        return 0;

    // 2. 每节车厢编号1 2 3 4 ... n
    int arr[n];
    for(int i=0; i<n; i++)
        arr[i] = i+1;

    // 3. n节车厢的总排列组合数：factorial = n！
    int factorial = 1;
    for (int i = 1; i <= n; i++) 
        factorial *= i;

    // 4. 分配n!个形如int [n];的小数组，用n!个指针统一管理
    int **result = (int **)calloc(factorial, sizeof(int *));
    for (int i = 0; i < factorial; i++)
        result[i] = (int *)calloc(n, sizeof(int));

    // 5. 生成1 2 3 4 ... n的全排列，放入result中
    permute(arr, 0, n - 1, result);


    printf("%d节车厢编号总共有 %d 种排列：\n", n, factorial);
    for(int i=0; i<factorial; i++)
    {
        if(is_valid(result[i], n))
            printf("√\n");
        else
            printf("×\n");
    }
    printf("其中共有 %d 种出站顺序\n", success);

    for(int i=0; i<factorial; i++)
        free(result[i]);
    free(result);

    return 0;
}
